/**
 * @author 雷明浩
 * @date 2025/7/4 17:51
 */
public class Solve {
    // 矩阵最长递增路径
    // https://www.nowcoder.com/practice/7a71a88cdf294ce6bdf54c899be967a2?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    private final int[] x = {-1,0,0,1};
    private final int[] y = {0,-1,1,0};
    private int maxLength = 0;
    private int pathLength = 0;
    private boolean[][] vis;
    public int solve (int[][] matrix) {
        // write code here
        vis = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                vis[i][j] = true;
                pathLength++;
                dfs(matrix, i, j);
                vis[i][j] = false;
                pathLength--;
            }
        }
        return maxLength;
    }

    private void dfs(int[][] matrix, int row, int col) {
        maxLength = Math.max(pathLength, maxLength);
        for (int i = 0; i < 4; i++) {
            int j = row + x[i];
            int k = col + y[i];
            if (j >= 0 && j < matrix.length
                    && k >= 0 && k < matrix[0].length
                    && !vis[j][k] && matrix[j][k] > matrix[row][col]) {
                vis[j][k] = true;
                pathLength++;
                dfs(matrix, j, k);
                vis[j][k] = false;
                pathLength--;
            }
        }
    }
}